\documentclass[a4paper,12pt,twocolumn]{article}
\usepackage{graphicx}
\usepackage{listings}
\usepackage[justification=centering]{caption}
\usepackage{subfigure}  
\usepackage{multirow}
\usepackage{balance}
\usepackage{gensymb}
\lstset{language=Matlab}
\lstset{breaklines}
\lstset{extendedchars=false}

\usepackage{amsmath,amsfonts,amsthm,amssymb}
\theoremstyle{definition}
\newtheorem{thm}{Theorem}
\newtheorem{exmp}{Example}
\newtheorem{defn}{Definition}
\newtheorem{lema}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{coro}{Corollary}


\renewcommand{\baselinestretch}{1.25}

%------------setlength----------------%
\setlength{\textwidth}{162mm}
%\setlength{\textheight}{190mm}
\setlength{\textheight}{231mm}
\setlength{\headheight}{-0.1cm}
\setlength{\topmargin}{-0.1cm}
\setlength{\oddsidemargin}{-0cm}
\setlength{\evensidemargin}{-0cm}

\setlength\columnsep{12pt}
\setlength\columnseprule{0.4pt}

\setlength{\parskip}{1mm}
\setlength{\unitlength}{1mm}
\setlength{\parindent}{2em}

\title{Numerical Analysis Homework \#2}

\author{Li Zhiqi\quad 3180103041 , }

\begin{document}
\maketitle
\section{Theoretical questions}
\uppercase\expandafter{\romannumeral1}.\\
With $f(x)=\frac{1}{x},x_0=1,x_1=2$, we have
  \begin{equation}
    p_1(f;x) = 1 - \frac{1}{2}(x-1) = -\frac{1}{2}x + \frac{3}{2} \nonumber
  \end{equation}
  Combining with $f''(x) = \frac{2}{x^3}$ implies
  \begin{eqnarray}
    \frac{1}{x} + \frac{1}{2}(x-3) = \frac{1}{[\xi(x)]^3}(x-1)(x-2) \nonumber\\
    \Rightarrow \frac{(x-1)(x-2)}{2x} = \frac{1}{[\xi(x)]^3}(x-1)(x-2) \nonumber \\
    \Rightarrow \xi(x) = (2x)^{\frac{1}{3}}, x\in [1,2].\nonumber
  \end{eqnarray}
  Then\\
  $\max_{x\in[1,2]}{\xi(x)}=\xi(2)=\sqrt[3]{4}$,\\
  $\min_{x\in[1,2]}{\xi(x)}=\xi(1)=\sqrt[3]{2}$,\\
  $\max_{x\in[1,2]}{f''(\xi(x))} = \max_{x\in[1,2]}{\frac{1}{x}} = 1.$\\\\
\uppercase\expandafter{\romannumeral2}.\\
Set
$$l_k(x) = \prod_{i\ne k;i=0}^{n} \frac{x - x_i}{x_k - x_i}$$
as elementary Lagrange interpolation polynomial. Apparently $l_k$ has degree $n$. Consider
\begin{equation}
  p(f;x) = \sum_{k=0}^{n}f_kl_k^2(x) .
\end{equation}
By the fact that $f_i \ge 0$, we get
$$\forall x \in \mathbb{R}, p(f;x) \ge 0.$$
Meanwhile, $p(f;x_i) = f_i$ holds resulting from $l_k(x_k) = 1$ and $l_k(x_i) = 0$ for any $i \ne k$. $p$ has degree $2n$
since every $l_k$ has degree $n$.\\
Therefore $p \in \mathbb{P}_{2n}^+$ and $p$ is the polynomial we find.\\\\
\uppercase\expandafter{\romannumeral3}.\\
\begin{itemize}
\item The induction basis holds for $n=0$ because $f[t]=e^t$. Suppose the conclusion holds for $n-1$, then we have
  \begin{align*}
    &f[t,t+1,\cdots,t+n]\\ \nonumber
    =&\frac{f[t,\cdots,t+n-1] - f[t+1,\cdots,t+n]}{-n}\\ \nonumber
    =&\frac{\frac{(e-1)^{n-1}}{(n-1)!}e^t-\frac{(e-1)^{n-1}}{(n-1)!}e^{t+1}}{-n}\\ \nonumber
    =&\frac{(e-1)^{n-1}}{n!}e^t(e-1) = \frac{(e-1)^n}{n!}e^t,
  \end{align*}
  where the first equation comes from Theorem 3.17, and the second equation results from induction hypothesis. So far we
  have completed the induction.\\
\item
  In formula
\begin{equation}
   f[t,t+1,\cdots,t+n] = \frac{(e-1)^n}{n!}e^t,
\end{equation}
set $t=0$, then we have
\begin{equation}
  f[0,1,\cdots,n] = \frac{(e-1)^n}{n!} = \frac{1}{n!}f^{(n)}(\xi).
\end{equation}
Combining with $f^{(n)}(\xi) = e^{\xi}$, we get
$$\xi = n\ln(e-1) > \frac{1}{2}n.$$
So $\xi$ locate at the right of the midpoint $n/2$.
\end{itemize}
\uppercase\expandafter{\romannumeral4}.\\
\begin{itemize}
\item The table of divided differences is as follows.
\begin{table}[!htp]
	\centering
	\setlength{\tabcolsep}{0.6mm}{
	\begin{tabular}{c|c c c c}
		$0\ $ & $5\ $ &  &  &\\	
		$1\ $ & $3\ $ & $-2\ $ & &  \\			
                $3\ $ & $5\ $ & $1\ $ & $1\ $ &  \\
                $4\ $ & $12\ $& $7\ $ & $2\ $ & $\frac{1}{4}\ $
	\end{tabular}
}
\end{table}\\
Hence
\begin{align*}
  p_3(f;x) &= 5 -2x + x(x-1) \\ \nonumber
             &+ \frac{1}{4}x(x-1)(x-3)\\ \nonumber
  &= \frac{1}{4}x^3 - \frac{9}{4}x + 5.\\ \nonumber
\end{align*}
\item We find
  \begin{equation}
    p_3'(f;x) = \frac{3}{4}x^2 - \frac{9}{4} = \frac{3}{4}(x^2 - 3).
  \end{equation}
  When $x \in (1,3)$, (4) implies $x_{min} = \sqrt{3}$, and $p_3(f;x_{min}) = -\frac{3}{2}\sqrt{3}+5.$
\end{itemize}
\newpage
\uppercase\expandafter{\romannumeral5}.\\
\begin{itemize}
\item The table of divided differences is as follows.
\begin{table}[!htp]
	\centering
	\setlength{\tabcolsep}{0.6mm}{
	\begin{tabular}{c|c c c c c c}
	  $0\ $ & $0\ $  &       &       &       &       &      \\	
          $1\ $ & $1\ $  &$1\ $  &       &       &       &      \\			
          $1\ $ & $1\ $  &$7\ $  &$6\ $  &       &       &      \\
          $1\ $ & $1\ $  &$7\ $  &$21\ $ &$15\ $ &       &      \\
          $2\ $ & $128\ $&$127\ $&$120\ $&$99\ $ &$42\ $ &      \\
          $2\ $ & $128\ $&$448\ $&$321\ $&$201\ $&$102\ $&$30\ $
	\end{tabular}
}
\end{table}\\
Hence
$$f[0,1,1,1,2,2] = 30.$$
\item By Corollary 3.22, we have
 \begin{align*}
   f[0,1,1,1,2,2] = \frac{1}{5!}f^{(5)}(\xi) = \frac{7!}{5!2!}\xi^2,
 \end{align*}
 which implies $\xi = \frac{\sqrt{70}}{7}.$
\end{itemize}
\uppercase\expandafter{\romannumeral6}.\\
\begin{itemize}
\item The table of divided differences is as follows.
\begin{table}[!htp]
	\centering
	\setlength{\tabcolsep}{0.6mm}{
	\begin{tabular}{c|c c c c c}
	  $0\ $ & $1\ $  &       &               &                &                 \\	
          $1\ $ & $2\ $  &$1\ $  &               &                &                 \\			
          $1\ $ & $2\ $  &$-1\ $ &$-2\ $         &                &                 \\
          $3\ $ & $0\ $  &$-1\ $ &$0\ $          &$\frac{2}{3}\ $ &                 \\
          $3\ $ & $0\ $  &$0\ $  &$\frac{1}{2}\ $&$\frac{1}{4}\ $ &$-\frac{5}{36}\ $
	\end{tabular}
}
\end{table}\\
Hence
\begin{align*}
   p_4(f;x) &= 1 + x - 2x(x-1)+\frac{2}{3}x(x-1)^2 \\ 
             &- \frac{5}{36}x(x-1)^2(x-3)\\ 
  &= -\frac{5}{36}x^4 + \frac{49}{36}x^3 - \frac{155}{36}x^2 +\frac{147}{36}x +1,\\ 
\end{align*}
and $p_4(f;2) = \frac{11}{18}.$

\item By Theorem 3.33, we have
 \begin{align*}
   R_4(f;x) &= f(x) - p_4(f;x)\\
   &= \frac{f^{(5)}(\xi)}{5!}x(x-1)^2(x-3)^2\\
     & \le \frac{M}{120}x(x-1)^2(x-3)^2.
 \end{align*}
 Therefore $R_4(f;2) \le \frac{M}{120}\cdot 2 = \frac{M}{60}.$
\end{itemize}
\uppercase\expandafter{\romannumeral7}.\\
By symmetry, we only prove former. We will prove it by induction.\\
For $k=1$,
\begin{align*}
  \bigtriangleup f(x) &= f(x+h)-f(h)\\
  &=h\cdot f[x_0,x_1] = k!h^kf[x_0,x_1].
\end{align*}
Suppose the formula holds for k, then
\begin{align*}
  \bigtriangleup^{k+1}f(x) &= \bigtriangleup^kf(x+h)-\bigtriangleup^kf(x)\\
                           &=k!h^kf[x_1,\cdots,x_{k+1}]\\
                            &\ -k!h^kf[x_0,\cdots,x_k]\\
                           &=k!h^k\cdot (k+1)h\cdot f[x_0,\cdots,x_{k+1}]\\
  &=(k+1)!h^{k+1}f[x_0,\cdots,x_{k+1}],
\end{align*}
where the first equation follows from definition of forward difference, the second from induction hypothesis, and the
third from Theorem 3.17.\\
\uppercase\expandafter{\romannumeral8}.\\
We will prove the conclusion by induction. For $n=1$,
\begin{align*}
  \frac{\partial }{\partial x_0}&f[x_0,x_1] =  \frac{\partial }{\partial x_0}[\frac{f(x_0)-f(x_1)}{x_0-x_1}]\\ 
  &=\frac{f'(x_0)(x_0-x_1)-(f(x_0)-f(x_1))}{(x_0 - x_1)^2}. 
    \end{align*}
    \begin{align*}
      f[x_0,x_0,x_1]&=\frac{f[x_0,x_0]-f[x_0,x_1]}{x_0-x_1}\\
                    &=\frac{f'(x_0)-\frac{f(x_0)-f(x_1)}{x_0-x_1}}{x_0-x_1}\\
      &=\frac{f'(x_0)(x_0-x_1)-(f(x_0)-f(x_1))}{(x_0 - x_1)^2}. 
    \end{align*}
    Hence $\frac{\partial }{\partial x_0}f[x_0,x_1] = f[x_0,x_0,x_1]$. Suppose the conclusion holds for $n$, then
    \begin{align*}
      &\quad \  \frac{\partial }{\partial x_0}f[x_0,x_1,\cdots,x_n,x_{n+1}]\\
      &=\frac{\partial }{\partial x_0}(\frac{f[x_0,\cdots,x_n]-f[x_0,\cdots,x_{n-1},x_{n+1}]}{x_n - x_{n+1}})\\
      &=\frac{f[x_0,x_0,x_1,\cdots,x_n] - f[x_0,x_0,x_1,\cdots,x_{n-1},x_{n+1}]}{x_n - x_{n+1}}\\
      &=f[x_0,x_0,x_1,\cdots,x_n,x_{n+1}],
    \end{align*}
    where the first and last step follow from Theorem 3.17, and the second from induction hypothesis. Then the induction
    has completed.\\
    If $f$ is differentiable at $x_i, i = 0,1,\cdots,n$, by Corollary 3.15, we have
    \begin{equation}
      \frac{\partial }{\partial x_i}f[x_0,x_1,\cdots,x_n] = f[x_i,x_0,x_1,\cdots,x_n,x_{n+1}]
    \end{equation}
    for $i = 0,1,\cdots,n$.\\
    \uppercase\expandafter{\romannumeral9}.\\
    Set
    $$x = \frac{a+b}{2} +t\frac{b-a}{2}.$$
    Then $x\in [a,b]$ implies $t\in [-1,1]$. We have
    \begin{align*}
     &\ \max_{x\in [a,b]}|a_0x^n+a_1x_{n-1}+\cdots+a_n|\\
      &=\max_{t\in [-1,1]}|a_0[\frac{a+b}{2} +t\frac{b-a}{2}]^n\\
      &\ + a_1[\frac{a+b}{2} +t\frac{b-a}{2}]^{n-1}+\cdots+a_n|\\
      &=\max_{t\in [-1,1]}|a_0(\frac{b-a}{2})^nt^n + \cdots|\\
      &\ge \frac{|a_0|(\frac{b-a}{2})^n}{2^{n-1}} = \frac{|a_0|(b-a)^n}{2^{2n-1}},
    \end{align*}
    where the last inequality follows from Corollary 3.43. Notice that "=" holds by adjusting $a_1,\cdots,a_n$
    appropriately , so
    \begin{align*}
     &\quad \ \min \max_{x\in [a,b]}|a_0x^n+a_1x_{n-1}+\cdots+a_n| \\
      &= \frac{|a_0|(b-a)^n}{2^{2n-1}}.
    \end{align*}
    \uppercase\expandafter{\romannumeral10}.\\
    Notice that
    \begin{equation}
      \left \| \hat{p}_n(x) \right \|_{\infty} = \max_{x\in [-1,1]}|\frac{T_n(x)}{T_n(a)}| = \frac{1}{T_n(a)},
    \end{equation}
    where the last step follows from $T_n(a) > 0$. Suppose the conclusion dose not hold. Then (6) implies that
    \begin{equation}
      \exists p \in \mathbb{P}_n^a,s.t. \max_{x\in [-1,1]}|p(x)|<\frac{1}{T_n(a)}.
    \end{equation}
    Consider the polynomial $Q(x) = \frac{T_n(x)}{T_n(a)} - p(x)$, then
    \begin{align*}
      Q(x_k') = \frac{(-1)^k}{T_n(a)} - p(x_k'), \quad \quad k=0,1,\cdots,n,
    \end{align*}
    where $x_k' = \cos\frac{k}{n}\pi.$ By (7), $Q(x)$ has alternating signs at these $n+1$ points. Hence $Q(x)$ must
    have $n$ zeros at [-1,1]. Notice that $Q(a) = 0$, which implies that $Q(x)$ has at least $n+1$ zeros. However, by
    the struction of $Q(x)$, the degree of $Q(x)$ is at most n. Therefore, $Q(x) \equiv 0$ and $p(x) =
    \frac{T_n(x)}{T_n(a)}$, which implies $\max_{x\in [-1,1]}p(x) = \frac{1}{T_n(a)}$. This is a contradiction to (7).
    Then we complete the proof.
\newpage    
\section{C++ programming}
Use \textbf{"make"} to generate and run an executable called \textbf{main}, which is the answer to the questions. Run it will show
all the numerical results and graphics by matlab. You're supposed to exit matlab to get the next plot.\\
Use \textbf{"make test"} to generate and run all the test file. The result will be shown immediately.\\
Use \textbf{"make doc"} to generate a pdf file called \textbf{doc.pdf}, which gives the answer to theoretical questions
and explanations for programming questions.\\\\
B. We list the results below.
\begin{align*}
&N =  2 : -0.0384615x^2+1\\
&N =  4 : 0.00530504x^4-0.171088x^2+1\\
  &N =  6 : -0.000840633x^6+0.0335319x^4\\
    &-0.351364x^2+1\\
  &N =  8 : 0.000137445x^8-0.00658016x^6\\
    &+0.0981875x^4-0.528121x^2+1
\end{align*}
Run Outputfile/B.m by matlab to get following plot.
\begin{figure}[!htp]   
	\centering
	\includegraphics[width=6cm]{Picture/F1.eps}
	\caption{Runge phenomenon}
\end{figure}
\newpage
\noindent C. The result will be shown after using "make" or runing the executable main.\\
Run Outputfile/C.m by matlab to get following plot.
\begin{figure}[!htp]   
	\centering
	\includegraphics[width=8cm]{Picture/F2.eps}
	\caption{Chebyshev interpolation}
\end{figure}\\
D. Interpolating result:
\begin{align*}
  &-0.0000202236x^9+0.00104059x^8\\
  &-0.0218757x^7+0.243041x^6-1.5383x^5\\
  &+5.50812x^4-10.0953x^3+7.16191x^2+75x.
\end{align*}
When $t = 10$s, \\
the position = $742.503$(feet), speed  = $48.3817$(feet per second).\\
To determine whether the car ever exceeds the 55mi/h (81 feet per second) speed limit,we show the speed-time relation by
prediction. Run Outputfile/D.m by matlab to get following plot.\\
\begin{figure}[!htp]   
	\centering
	\includegraphics[width=8cm]{Picture/F3.eps}
	\caption{speed-time relation}
      \end{figure}
      \newpage
\noindent We find that the car ever exceeds the 55mi/h (81 feet per second) speed limit.\\\\
E.For sample1, average weight curve:
\begin{align*}
  &0.000041477x^6-0.00371557x^5\\
  &+0.128281x^4-2.11512x^3\\
  &+16.2855x^2-43.0127x+6.67
\end{align*}
For sample2, average weight curve:
\begin{align*}
  &0.0000086768ex^6-0.000777473x^5\\
  &+0.0265858x^4-0.424283x^3\\
  &+2.98227x^2-5.85018x+6.67
\end{align*}
Next we show the weight-time relation between 28 and 43 days by prediction. Run Outputfile/E.m by matlab to get
following plot.\\
\begin{figure}[!htp]   
	\centering
	\includegraphics[width=8cm]{Picture/F4.eps}
	\caption{weight-time relation}
      \end{figure}\\
      \newpage
\noindent We find both of samples will not die after another 15 days.
\end{document}
